/**
 * 验证二叉搜索树
 */

//中序遍历
var isValidBST = (root) => {
  const quene = []
  const dfs = (root) => {
    if (!root) return
    root.left && dfs(root.left)
    quene.push(root.val)
    root.right && dfs(root.right)
  }
  dfs(root)
  for (let i = 0; i < quene.length - 1; i++) {
    if (quene[i] >= quene[i + 1]) return false
  }
  return true
};

//递归
const isValidTree = (root, min = -Infinity, max = +Infinity) => {
  if (root == null) return true;
  if (min !== null && root.val <= min) return false
  if (max !== null && root.val >= max) return false

  return isValidTree(root.left, min, root.val) && isValidTree(root.right, root.val, max)
}
